UVa/11846 - Finding Seats Again/11846.2.cpp

   1 // Accepted
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 namespace IO {
  29 #define MAXBUFF (1<<18)
  30    char inBuffer[MAXBUFF], *pIn = inBuffer+MAXBUFF;
  31    char outBuffer[MAXBUFF], *pOut = outBuffer;
  32
  33    inline char read_char() {
  34       if( pIn == inBuffer+MAXBUFF ) {
  35          fread( inBuffer, 1, MAXBUFF, stdin );
  36          pIn = inBuffer;
  37       }
  38       return *pIn++;
  39    }
  40
  41    inline int read_int() {
  42       char c;
  43       while( !isdigit(c = read_char()) );
  44       int ret = c-'0';
  45       while( isdigit(c = read_char()) ) ret = ret * 10 + c-'0';
  46       return ret;
  47    }
  48
  49    void flush() {
  50       fwrite( outBuffer, 1, pOut-outBuffer, stdout );
  51       pOut = outBuffer;
  52    }
  53
  54    inline void write( char c ) {
  55       if( pOut == outBuffer+MAXBUFF ) {
  56          fwrite( outBuffer, 1, MAXBUFF, stdout );
  57          pOut = outBuffer;
  58       }
  59       *pOut++ = c;
  60    }
  61 }
  62
  63 const int MAXN = 20;
  64 const int MAXK = 26;
  65
  66 struct region {
  67     short r1, r2, c1, c2;
  68     region() {}
  69     region(short r1, short r2, short c1, short c2) : r1(r1), r2(r2), c1(c1), c2(c2) {}
  70 };
  71
  72 int N, K;
  73 char mat[MAXN+1][MAXN+1];
  74 region regions[MAXK * 32];
  75 int totalRegions;
  76
  77 inline void fillRegion(const region &r, char letter) {
  78     for (int i = r.r1; i <= r.r2; ++i) {
  79         for (int j = r.c1; j <= r.c2; ++j) {
  80             mat[i][j] = letter;
  81         }
  82     }
  83 }
  84
  85 inline bool isEmpty(const region &r) {
  86     for (int i = r.r1; i <= r.r2; ++i) {
  87         for (int j = r.c1; j <= r.c2; ++j) {
  88             if (mat[i][j] != '.') return false;
  89         }
  90     }
  91     return true;
  92 }
  93
  94 bool backtrack(int cell, char face) {
  95     int r = cell / N;
  96     int c = cell % N;
  97
  98     if (r >= N or c >= N) {
  99         for (int i = 0; i < N; ++i) {
 100             for (int j = 0; j < N; ++j) {
 101                 IO::write(mat[i][j]);
 102             }
 103             IO::write('\n');
 104         }
 105         return true;
 106     }
 107
 108     if (mat[r][c] != '.') return backtrack(cell + 1, face);
 109
 110     for (int k = 0; k < totalRegions; ++k) {
 111         const region &rg = regions[k];
 112         if (r != rg.r1 or c != rg.c1) continue;
 113         if (!isEmpty(rg)) continue;
 114         fillRegion(rg, face);
 115         if (backtrack(cell + 1, face + 1)) return true;
 116         fillRegion(rg, '.');
 117     }
 118     return false;
 119 }
 120
 121 int main(){
 122     while (true) {
 123         N = IO::read_int();
 124         K = IO::read_int();
 125         if (N == 0 and K == 0) break;
 126
 127         for (int i = 0; i < N; ++i) {
 128             for (int j = 0; j < N; ++j) {
 129                 char c = IO::read_char(); while (isspace(c)) c = IO::read_char();
 130                 mat[i][j] = c;
 131             }
 132         }
 133
 134         totalRegions = 0;
 135
 136         for (int i = 0; i < N; ++i) {
 137             for (int j = 0; j < N; ++j) {
 138                 if (mat[i][j] == '.') continue;
 139                 int size = mat[i][j] - '0';
 140                 mat[i][j] = '.';
 141                 for (int width = 1; width <= size; ++width) {
 142                     if (size % width != 0) continue;
 143                     int height = size / width;
 144                     for (int ii = max(0, i - height + 1); ii + height - 1 < N and ii <= i; ++ii) {
 145                         for (int jj = max(0, j - width + 1); jj + width - 1 < N and jj <= j; ++jj) {
 146                             region r(ii, ii + height - 1, jj, jj + width - 1);
 147                             if (isEmpty(r)) {
 148                                 regions[totalRegions++] = r;
 149                             }
 150                         }
 151                     }
 152                 }
 153                 mat[i][j] = '0' + size;
 154             }
 155         }
 156
 157         for (int i = 0; i < N; ++i) {
 158             for (int j = 0; j < N; ++j) {
 159                 mat[i][j] = '.';
 160             }
 161         }
 162         backtrack(0, 'A');
 163     }
 164     IO::flush();
 165     return 0;
 166 }